package com.base.leetcode;

import com.base.dataStructure.Tree.TreeNode;
import org.springframework.context.annotation.Bean;

import java.util.LinkedList;

/**
 * @Author: hdhao
 * @Create: 2023/4/9 - 14:32
 * @Version: v1.0
 */
//二叉搜索树的范围和
public class Leetcode938 {
    //中序遍历实现
    public int rangSumBST(TreeNode node, int low, int high) {
        TreeNode p = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode pop = stack.pop();
                if (pop.val > high) {
                    break;
                }
                //处理值
                if (pop.val >= low) {
                    sum += pop.val;
                }
                p = pop.right;
            }
        }
        return sum;
    }

    //递归实现
    public int rangSumBST1(TreeNode node, int low, int high) {
        if (node == null) {
            return 0;
        }
        if (node.val < low) {
            return rangSumBST1(node.right, low, high);
        }
        if (node.val > high) {
            return rangSumBST1(node.left, low, high);
        }
        //在范围内
        return node.val + rangSumBST1(node.left, low, high) +
                rangSumBST1(node.right, low, high);
    }
}
